package com.binarysorttree;

import java.util.HashMap;
import java.util.Map;

public class BinarySortTree {
    private Node root;

    /**
     * 二叉排序树添加结点
     */
    public void add(Node node) {
        if (root == null) {
            root = node;
        } else {
            root.add(node);
        }
    }

    /**
     * 中序遍历
     */
    public void infixOrder() {
        if (root == null) {
            System.out.println("该树为空数，无法进行遍历");
        } else {
            root.infixOrder();
        }
    }

    /**
     * 查找指定value的结点，用map保存该结点和父节点
     */
    public void searchNodeAndParentNode(int value, Map<String, Node> map) {
        if (root == null) {
            System.out.println("树中没有元素");
            return;
        } else {
            root.search(value, map);
        }
    }

    /**
     * 删除结点
     */
    public void deleteNode(int value, Map<String, Node> map) {
        if (root == null) {
            return;
        } else {
            searchNodeAndParentNode(value, map);
            //查找待删除结点和该结点的父节点
            Node curNode = map.get("curNode");
            Node parNode = map.get("parNode");
            //如果没有找到要删除的结点，直接返回
            if (curNode == null) {
                return;
            }
            //二叉排序树只有一个结点的情况，parNode = null的情况, 则直接删除
            if (root.left == null && root.right == null) {
                root = null;
                return;
            }
            //1.删除叶子结点
            if (curNode.left == null && curNode.right == null) {
                if (parNode.left != null && parNode.left.value == curNode.value) {
                    parNode.left = null;
                } else if (parNode.right != null && parNode.right.value == curNode.value) {
                    parNode.right = null;
                }
            } else if (curNode.left != null && curNode.right != null) {
                //2.删除具有两棵子树的结点,从curNode的右子树找到最小的结点删除并替换
                //或从curNode的左子树中找最大的
                int minValue = delRightTreeMin(curNode.right, map);
                curNode.value = minValue;
            } else {
                //3.删除具有一棵子树的结点
                //bug:parNode可能为空，即只有一棵子树的结点，分别为根结点和一个孩子结点
                if (curNode.left != null) {
                    if (parNode != null) {
                        if (parNode.left.value == value) {
                            parNode.left = curNode.left;
                        } else {
                            parNode.right = curNode.left;
                        }
                    } else {
                        root = curNode.left;
                    }
                } else {
                    if (parNode != null) {
                        if (parNode.left.value == value) {
                            parNode.left = curNode.right;
                        } else {
                            parNode.right = curNode.right;
                        }
                    } else {
                        root = curNode.right;
                    }
                }
            }
        }
        map.clear();
    }

    /**
     * @param node 以node为根结点，找到node右子树的最小值并删除
     */
    public int delRightTreeMin(Node node, Map<String, Node> map) {
        Node temp = node;
        if (temp.left != null) {
            temp = temp.left;
        }
        deleteNode(temp.value, map);
        return temp.value;
    }


}
